This invention relates to the field of electronic generation of bit signals in a random order of 1's and 0's, which may be used in that form or transferred to another numerical base, such as the base ten.
It is desirable to be able to generate random numbers for use in computers, for example as part of an encryption procedure. Many circuits operate on the basis of feedback of information from one or more output terminals to one or more input terminals in a shift register, but the generation of numbers in such circuits, while apparently random, is not entirely so. The numbers so generated are usually referred to as pseudorandom numbers. Other circuits generate or use random signals, essentially noise signals, to generate more nearly truly random numbers.
U.S. Pat. No. 3,612,845 to Lawlor describes the generation of random binary numbers by sampling the magnitude of the output signal of a random noise source. The samples constitute a regularly occurring train of pulses of random amplitude. The pulse train is passed through a threshold circuit and all pulses above the threshold levels are deemed to correspond to 1's, while all those below the threshold are deemed to constitute 0's. Since all of the bits are generated by direct interaction of the clock signal with the noise signal, the transition from a 1 to a 0 would be dependent upon the rate of change of the noise signal, and any slowing down of the rate of change, as for example by passing the signal through a low pass filter, which Lawlor does, would lead to a tendency to generate a plurality of successive bits of the same type and would violate one of the fundamental requirements of a true random binary number generator: no matter whether a given bit is a 1 or a 0, the probability that the next bit will be a 1 is equal to the probability that it will be a 0.
U.S. Pat. No. 3,848,586 to Suzuki describes a system that utilizes signals similar to random signals but does not do so for the purpose of providing a random sequence of 1's and 0's.
U.S. Pat. No. 4,183,088 to Simmons describes the generation of a random sequence of 1's and 0's by generating pulses of random width and sampling them at regular intervals. The number of sampling pulses in each random width pulse is either odd or even and that fact is used to determine whether the random width pulse constitutes a 1 or a 0.
U.S. Pat. No. 4,327,419 to Deutsch et al. describes the utilization of a noise signal as a basis for generating a musical signal but not a random number sequence.
It is an object of the invention to provide a circuit for generating electrical signals representing 1's and 0's in random order.
Another object is to provide a method for generating random-order bit signals.
A further object is to generate random-order 1 and 0 bit signals without generating detectable ambiguous signals, each representative of both 1 and 0.
Briefly, the present invention is directed to a random number signal generator comprising: means to generate a random amplitude signal; first means to determine when the random amplitude signal has made an excursion farther in one polarity from a zero value than a first level and then has returned to an intermediate range closer to the zero value than the first level to generate a signal having a first binary value; and second means to determine when the random amplitude signal has made an excursion farther in the opposite polarity from the zero value than a second level and has returned to the intermediate range to complete the generation of a signal having a second binary value.
In accordance with the present invention, a random sequence of 1's and 0's is generated by utilizing the output signal of a noise generator. The amplitude of this signal varies randomly above a predetermined positive level and below a predetermined negative level, and each excursion of the voltage beyond the respective levels is detected in first and second detectors, respectively. The random noise signal is also detected in a third detector when it is within an intermediate range between the two levels just mentioned. The purpose of detecting that the amplitude of the random signal has reached the positive level and has subsequently diminished to the intermediate range is that both of those events must occur in that sequence to generate a signal arbitrarily designated as a 1. The occasions when the signal randomly becomes more negative than the negative level, so as to actuate the second detector, and thereafter returns to the intermediate range are designated as 0's. The output of the first detector when the signal exceeds the positive voltage bound sets a first flip-flop arbitrarily designated as the 1's flip-flop, and it remains set until a reset voltage is produced when the random signal thereafter returns to the intermediate range. In the same manner, a 0's flip-flop is set by the output of the second detector when the random signal becomes more negative than the predetermined negative bound, and this flip-flop remains set until the random signal returns to the intermediate range.
In order to correlate some part of the signals representing 1's and 0's at the outputs of the two flip-flops with a clock signal, such as is utilized in a computer, the signal generated when the random signal is within the intermediate range is applied to a D-type flip-flop that is clocked by the clock signal. The output of the latter flip-flop circuit is combined with the clock signal to generate the reset signal as a series of pulses corresponding to the clock pulses that occur during the time the random signal is within the intermediate range. It is the first of these reset pulse signals that resets the 1's flip-flop and the 0's flip-flop, according to which one of them is in the set condition at the time the reset signal is generated.
It is possible for the random signal to change so rapidly that it passes through the intermediate band between successive clock pulses, and in that case, it would be possible for the 1's flip-flop to be still set when the 0's flip-flop is set. As a result, the output signals of these two flip-flops cannot be used directly to indicate whether a 1 or a 0 has been generated, and in order to eliminate this ambiguous condition, the outputs of the two flip-flops are applied to an Exclusive OR gate, which allows an output signal to pass through only when the two input signals are of different value, indicating that one of the flip-flops is set and the other is not. By making the clock signal have a high repetition rate, it is inevitable that the signal will eventually be in the intermediate range long enough to be coincident with at least one clock pulse so as to generate at least one reset pulse, which is all that is required to reset either or both the 1's flip-flop and the 0's flip-flop.
The 1's and 0's are accumulated in the order in which they are generated, after removal of the previously mentioned ambiguity, by clocking each of them into a shift register. Since the clocking has to have the same degree of randomness as the rate at which the 1 and 0 bits are generated, the random bit clock signal is produced at the completion of each bit generation, whether it is a 1 bit or a 0 bit. This random bit clock signal is then used to clock the output of one of the flip-flops, either the 1's flip-flop or the 0's flip-flop, into a shift register. It is unnecessary to clock both of the flip-flops, because at the time of clocking, the signal being clocked in will either be present or not. If it is the output of the 1's flip-flop that is being clocked in, a signal present in its output at the time of clocking will be a 1's signal. When a clock signal is generated during the production of a 0 signal in the 0's flip-flop, there will be no output from the 1's flip-flop, and this condition will be clocked into the shift register as a 0.
In order to transfer the random sequence of 1's and 0's out of the shift register, the random bit clock signal may be applied to a counter to count a suitable number of pulses which can be read by a microprocessor. At a suitable count, the microprocessor can then generate a signal to be applied to the shift register to transfer the existing bits to a data bus. At the same time, the counter is returned to its initial condition to begin a new count. In this way, the random sequence of 1's and 0's in the shift register at the time they are transferred out can be transformed into a decimal signal by applying a sequence of four such bit signals to a binary-to-decimal converter.